Searching Analysis

Consider a finite collection of element. Finding whether element exsists in collection is known as Searching. Following are some of the comparision based Searching Algorithms.

Linear Search
Binary Search

Before looking at the analysis part, we shall examine the Language in built methods to searching

The `in` operator and `list.index()`

We have already seen the in operator in several contexts. Let's see the working of in operator again



In [1]:

    
x = list(range(10))



In [2]:

    
x









    Out[2]:





[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]



In [3]:

    
6 in x









    Out[3]:





True



In [4]:

    
100 in x









    Out[4]:





False



In [5]:

    
x.index(6)









    Out[5]:





6



In [6]:

    
x.index(100)









    



---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-6-0f87238c301b> in <module>()
----> 1 x.index(100)

ValueError: 100 is not in list

Standard `import` statement



In [16]:

    
from openanalysis.searching import SearchingAlgorithm,SearchAnalyzer
%matplotlib inline
%config InlineBackend.figure_formats={"svg", "pdf"}

SearchingAlgorithm is the base class providing the standards to implement searching algorithms, SearchAnalyzer analyses the algorithm

`SearchingAlgorithm` class

Any searching algorithm, which has to be implemented, has to be derived from this class. Now we shall see data members and member functions of this class.

Data Members

name - Name of the Searching Algorithm
count - Holds the number of basic operations performed

Member Functions

__init__(self, name): - Initializes algorithm with a name
search(self, array, key): _ The base searching function. Sets count to 0. array is 1D numpy array,key is the key of element to be found out

An example .... Binary Search

Now we shall implement the class BinarySearch



In [17]:

    
class BinarySearch(SearchingAlgorithm):                    # Inheriting
    def __init__(self):
        SearchingAlgorithm.__init__(self, "Binary Search") # Initailizing with name

    def search(self, arr, key):
        SearchingAlgorithm.search(self, arr, key)          # call base class search
        low, high = 0, arr.size - 1
        while low <= high:
            mid = int((low + high) / 2)
            self.count += 1                                # Increment for each basic operation performed
            if arr[mid] == key:
                return True
            elif arr[mid] < key:
                low = mid + 1
            else:
                high = mid - 1
        return False

`SearchAnalyzer` class

This class provides the visualization and analysis methods. Let's see its methods in detail

__init__(self, searcher): Initializes visualizer with a Searching Algorithm.
- searcher is a class, which is derived from SearchingAlgorithm

analyze(self, maxpts=1000):
- Plots the running time of searching algorithm by searching in 3 cases
- Key is the first element, Key is the last element, Key at random index
- Analysis is done by inputting sorted integer arrays with size staring from 100, and varying upto maxpts in the steps of 100, and counting the number of basic operations
- maxpts Upper bound on size of elements chosen for analysing efficiency



In [18]:

    
bin_visualizer = SearchAnalyzer(BinarySearch)









    





<matplotlib.figure.Figure at 0x7ff57329b978>



In [19]:

    
bin_visualizer.analyze(progress=False)









    



Please wait while analyzing Binary Search Algorithm

Note $\mathcal{O}(\log{}n)$ performance in all cases

`compare(algs)`

algs is a list of classes derived from SearchingAlgorithm. It performs tests and plots the bar graph comapring the number of basic operations performed by each algorithm.

Example File

You can see more examples at Github

Searching Analysis

The in operator and list.index()

Standard import statement

SearchingAlgorithm class